Java.util package

In this module, you will learn……………

Introduction

Enumeration Interface

Collection Interface

Collections class

Iterator Interface

Set Interface

ListIterator Interface

HashSet

Object Ordering(Comparator)

TreeSet

SortedSet

List Interface

ArrayLists

Vector

Map Interface

SortedMap

TreeMap

A collection (sometimes called a container) is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve and manipulate data, and to transmit data from one method to another. Collections typically represent data items that form a natural group, like a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a collection of name-to-phone-number mappings).

A collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain three things:

Interfaces: abstract data types representing collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages like Java, these interfaces generally form a hierarchy.

Implementations: concrete implementations of the collection interfaces. In essence, these are reusable data structures.

Algorithms: methods that perform useful computations, like searching and sorting, on objects that implement collection interfaces. These algorithms are said to be polymorphic because the same method can be used on many different implementations of the appropriate collections interface.

 

An object that implements the Enumeration interface generates a series of elements, one at a time. Successive calls to the nextElement method return successive elements of the series. The Enumeration interface is defines as follows

public interface Enumeration

The Enumeration Interface defines the methods by which you can enumerate(obtain one at a time) the elements in a collection of objects.Enumeration specifies the two methods:

public boolean hasMoreElements()

Tests if this enumeration contains more elements.

public Object nextElement()

Returns the next element of this enumeration if this enumeration object has at least one more element to provide.

For Example,

import java.util.Enumeration

class Enum implements Enumeration

{

private int count = 0;

private boolean more = true;

public boolean hasMoreElements()

{

return more;

}

public Object nextElement()

{

count++;

if (count > 4)

more = false;

return new Integer(count);

}

}

class EnumerateDemo

{

public static void main(String args[])

{

Enumeration enum = new Enum();

 

while(enum.hasMoreElements())

{

System.out.println(enum.nextElement());

}

}

}

The output of this program is:

1

2

3

4

5

The Collection interface specifies the contract that all collections should implement. Some of the operations in the interface are optional meaning that a collection may choose not to provide a proper implementation of such an operation.In such a case UnsupportedOperationException is thrown when an optional operation is invoked.

The Collection interface is shown below:

public interface Collection

{

// Basic Operations

int size();

boolean isEmpty();

boolean contains(Object element);

boolean add(Object element); // Optional

boolean remove(Object element); // Optional

Iterator iterator();

// Bulk Operations

boolean containsAll(Collection c);

boolean addAll(Collection c); // Optional

boolean removeAll(Collection c); // Optional

boolean retainAll(Collection c); // Optional

void clear(); // Optional

// Array Operations

Object[] toArray();

Object[] toArray(Object a[]);

Basic Operations

The basic operations are used to query collection about its contents and add and remove elements.

public int size()

Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

 

public boolean isEmpty()

Returns true if this collection contains no elements.

public boolean contains(Object o)

Returns true if this collection contains the specified element. More formally, returns true if and only if this collection contains at least one element e such that (o==null ? e==null : o.equals(e)).

public boolean add(Object o)

Ensures that this collection contains the specified element (optional operation). Returns true if this collection changed as a result of the call. (Returns false if this collection does not permit duplicates and already contains the specified element.)

public boolean remove(Object o)

Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if this collection contains one or more such elements. Returns true if this collection contained the specified element (or equivalently, if this collection changed as a result of the call).

The add() and remove() methods return true if the collection was modified as a result of the operation.The contains() method checks for membership.

These operations perform on a collection as a single unit.

public boolean containsAll(Collection c)

Returns true if this collection contains all of the elements in the specified collection.

public boolean addAll(Collection c) //optional

Adds all of the elements in the specified collection to this collection (optional operation). The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.)

public boolean removeAll(Collection c) //optional

Removes all this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection.

public boolean retainAll( Collection c) //optional

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

public void clear() // optional

Removes all of the elements from this collection (optional operation). This collection will be empty after this method returns unless it throws an exception.

These operations allow conversion of collections to arrays.

public Object[] toArray()

Returns an array containing all of the elements in this collection. If the collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

public Object[] toArray(Object[] a)

Returns an array containing all of the elements in this collection whose runtime type is that of the specified array. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection.

java.lang.Object

|

+--java.util.Collections

public class Collections extends Object

This class consists exclusively of static methods that operate on or return collections.

The common methods in Collections are:

public static void sort(List list)

Sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)

public static void shuffle( List list)

Randomly permutes the elements in a List. (Shown above.)

public static void reverse( List l)

Reverses the order of the elements in a List.

public static void fill(List list, Object o)

Overwrites every element in a List with the specified value.

public static void copy(List dest, List src)

Copies the source List into the destination List.

public static int binarySearch(List list, Object key)

Searches for an element in an ordered List using the binary search algorithm.

An iterator allows serial access to the elements of a collection.

public interface Iterator

An iterator over a collection. Iterator takes the place of Enumeration in the Java collections framework. Iterators differ from enumerations in two ways:

Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics.

Method names have been improved.

The Iterator interface is shown below:

public interface Iterator

{

boolean hasNext();

Object next();

void remove(); // Optional

}

The methods in Iterator interface are:

public boolean hasNext()

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

public Object next()

Returns the next element in the in iteration.

public void remove()

Removes from the underlying collection the last element returned by the iterator (optional operation). This method can be called only once per call to next. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

For Example,

The following snippet shows you how to use an Iterator to filter a Collection, that is, to traverse the collection, removing every element that does not satisfy some condition:

static void filter(Collection c)

{

for (Iterator i = c.iterator(); i.hasNext(); )

if (!cond(i.next()))

i.remove();

}

Unlike other implementations of Collection, implementations of Set will not allow duplicate elements. The Set interface does not define any new methods, but adds the restriction that duplicates are prohibited. A Set models a mathematical set

The Set interface is shown below:

public interface Set

{

// Basic Operations

int size();

boolean isEmpty();

boolean contains(Object element);

boolean add(Object element); // Optional

boolean remove(Object element); // Optional

Iterator iterator();

// Bulk Operations

boolean containsAll(Collection c);

boolean addAll(Collection c); // Optional

boolean removeAll(Collection c); // Optional

boolean retainAll(Collection c); // Optional

void clear(); // Optional

// Array Operations

Object[] toArray();

Object[] toArray(Object a[]);

}

Implementations acting as multisets (a.k.a bags) that allow duplicate elements cannot be implemented using Set interface, since elements must be unique in a set.

The JDK contains two general-purpose Set implementations.

HashSet, which stores its elements in a hash table, is the best-performing implementation. TreeSet, which stores its elements in a red-black tree, guarantees the order of iteration.

 

For Example (for Basic Operations),

import java.util.*;

public class FindDups

{

public static void main(String args[])

{

Set s = new HashSet();

for (int i=0; i<args.length; i++)

if (!s.add(args[i]))

System.out.println("Duplicate detected: "+args[i]);

System.out.println(s.size()+" distinct words detected: "+s);

}

}

On running the program with following options

% java FindDups i came i saw i left

Duplicate detected: i

Duplicate detected: i

4 distinct words detected: [came, left, saw, i]

Note that the example code always refers to the collection by its interface type (Set), rather than by its implementation type (HashSet). This is a strongly recommended programming practice, as it gives you the flexibility to change implementations merely by changing the constructor.

If you want the program to print the word list in alphabetical order, all you have to do is to change the set's implementation type from HashSet to TreeSet. Making this trivial one-line change causes the command line in the previous example to generate the following output:

% java FindDups i came i saw i left

Duplicate word detected: i

Duplicate word detected: i

4 distinct words detected: [came, i, left, saw]

For Example(for Bulk Operations),

import java.util.*;

public class FindDups2

{

public static void main(String args[])

{

Set uniques = new HashSet();

Set dups = new HashSet();

for (int i=0; i<args.length; i++)

if (!uniques.add(args[i]))

dups.add(args[i]);

uniques.removeAll(dups); // Destructive set-difference

System.out.println("Unique words: " + uniques);

System.out.println("Duplicate words: " + dups);

}

}

Run the revised program with the same same argument list we used before:

% java FindDups2 i came i saw i left

Unique words: [came, left, saw]

Duplicate words: [i]

public class HashSet extends AbstractSet implements Set, Cloneable, Serializable

Linked lists and arrays let you specify in which order you want to arrange the elements. However, if you are looking for a particular element and you don't remember its position, then you need to visit all elements until you find a match. That can be time-consuming if the collection contains many elements. If you don't care about the ordering of the elements, then there are data structures that let you find elements much faster. The drawback is that these data structures give you no control over the order in which the elements appear. The data structures organize the elements in an order that is convenient for their own purposes.

A well-known data structure for finding objects quickly is the hash table. A hash table computes an integer, called the hash code, for each object.

A hash table is,

Comparator

public interface Comparator

The Comparable interface has been covered in java.lang package.

The Comparable interface provides a natural ordering for a class, which allows objects of that class to be sorted automatically. But what if you want to sort some objects in some order other than their natural order? Or what if you want to sort some objects that don't implement Comparable? To do either of these things, you'll need to provide a comparator. A Comparator is simply an object that encapsulates an ordering.

public int compare(Object o1, Object o2)

The compare method compares its two arguments, returning a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for the Comparator, the compare method throws a ClassCastException.

For Example,

public class EmployeeRecord implements Comparable

{

public Name name();

public int employeeNumber();

public Date hireDate();

...

}

Let's assume that the natural ordering of EmployeeRecord objects is Name-ordering i.e on employee name. Unfortunately the boss has asked us for a list of employees in order of seniority. Here's a program that will produce the required list:

import java.util.*;

class EmpSort

{

static final Comparator SENIORITY_ORDER = new Comparator()

{

public int compare(Object o1, Object o2) {

EmployeeRecord r1 = (EmployeeRecord) o1;

EmployeeRecord r2 = (EmployeeRecord) o2;

return r2.hireDate().compareTo(r1.hireDate());

}

};

static final Collection employees = ... ; // Employee Database

public static void main(String args[])

{

List emp = new ArrayList(employees);

Collections.sort(emp, SENIORITY_ORDER);

System.out.println(emp);

}

}

The Comparator in the above program is reasonably straightforward. It casts its arguments to EmployeeRecord, and relies on the natural ordering of Date applied to the hireDate() accessor method. Note that the Comparator passes the hire-date of its second argument to its first, rather than vice-versa. This is because the employee who was hired most recently is least senior: sorting in order of hire-date would put the list in reverse seniority-order

public interface SortedSet extends Set

A SortedSet that maintains its elements in ascending order, sorted according to the elements' natural order, or according to a Comparator provided at SortedSet creation time.

public interface SortedSet extends Set

{

// Range-view

SortedSet subSet(Object fromElement, Object toElement);

SortedSet headSet(Object toElement);

SortedSet tailSet(Object fromElement);

// Endpoints

Object first();

Object last();

Consider that dictionary is an object of SortedSet of strings:

public SortedSet headSet(Object toElement)

Returns a view of the portion of this sorted set whose elements are strictly less than toElement. The returned sorted set is backed by this sorted set, so changes in the returned sorted set are reflected in this sorted set, and vice-versa. The returned sorted set supports all optional set operations.

Following code allows you to view the dictionary as "volume" (a-m):

SortedSet volume1 = dictionary.headSet("n");

public SortedSet tailSet(Object fromElement)

Returns a view of the portion of this sorted set whose elements are greater than or equal to fromElement. The returned sorted set is backed by this sorted set, so changes in the returned sorted set are reflected in this sorted set, and vice-versa. The returned sorted set supports all optional set operations.

Following code allows you to view the dictionary as "volume" (n-z):

SortedSet volume2 = dictionary.tailSet("n");

public SortedSet subSet(Object fromElement, Object toElement)

Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive. (If fromElement and toElement are equal, the returned sorted set is empty.) The returned sorted set is backed by this sorted set, so changes in the returned sorted set are reflected in this sorted set, and vice-versa. The returned sorted set supports all optional set operations that this sorted set supports

Following Example,tells you how many words between "doorbell" and "pickle", including "doorbell" but excluding "pickle", are contained in a SortedSet of strings called dictionary:

int count = dictionary.subSet("doorbell", "pickle").size();

public Object first()

Returns the first (lowest) element currently in this sorted set

public Object last()

Returns the last (highest) element currently in this sorted set.

 

public class TreeSet extends AbstractSet implements SortedSet, Cloneable, Serializable

The TreeSet class is similar to the hash set, with one added improvement. A tree set is a sorted collection. You insert elements into the collection in any order. When you iterate through the collection, the values are automatically presented in sorted order.

TreeSet()

Constructs a new, empty set, sorted according to the elements' natural order.

TreeSet(Collection c)

Constructs a new set containing the elements in the specified collection, sorted according to the elements' natural order.

TreeSet(Comparator c)

Constructs a new, empty set, sorted according to the given comparator.

TreeSet(SortedSets)

Constructs a new set containing the same elements as the given sorted set, sorted according to the same ordering.

public interface ListIterator extends Iterator

public interface ListIterator extends Iterator

public boolean hasPrevious()

Returns true if this list iterator has more elements when traversing the list in the reverse direction.

public Object previous()

Returns the previous element in the list. This method may be called repeatedly to iterate through the list backwards, or intermixed with calls to next to go back and forth.

public int nextIndex()

Returns the index of the element that would be returned by a subsequent call to next.

public int previousIndex()

Returns the index of the element that would be returned by a subsequent call to previous.

public interface List extends Collection

Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

Positional Access: manipulate elements based on their numerical position in the list.

Search: search for a specified object in the list and return its numerical position.

List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.

Range-view: perform arbitrary range operations on the list.

The List interface is shown below:

public interface List extends Collection

{

// Positional Access

Object get(int index);

Object set(int index, Object element); // Optional

void add(int index, Object element); // Optional

Object remove(int index); // Optional

abstract boolean addAll(int index, Collection c); // Optional

// Search

int indexOf(Object o);

int lastIndexOf(Object o);

// Range-view

List subList(int from, int to);

}

Lists are collections which maintain their elements in order(also called a sequence), and can contain duplicates.This additional functionality is provided by the following methods:

public Object get(int index)

Returns the element at the specified position in this list.

public Object set(int index, Object element)

Replaces the element at the specified position in this list with the specified element

public void add(int index, Object element)

Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

public boolean remove(Object o)

Removes the first occurrence in this list of the specified element (optional operation). If this list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists).

public boolean addAll(Collection c)

Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator (optional operation).

There are methods for element search which are:

public int indexOf(Object o)

Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

public int lastIndexOf(Object o)

Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element. More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and bidirectional access in addition to the normal operations that the Iterator interface provides.

Three implementations of List interface are provided in the java.util package ArrayList,Vector and LinkedList.

public class ArrayList extends AbstractList implements List, Cloneable, Serializable.

Resizable-array implementation of the List interface.Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

public class LinkedList extends AbstractSequentialList implements List, Cloneable, Serializable

Removing an element from the middle of an array is very expensive since all array elements beyond the removed one must be moved toward the beginning of the array The same is true for inserting elements in the middle.

Another well-known data structure, the linked list, solves this problem.

In java, arrays are of fixed length. Once created they cannot grow or shrink. This means that you must know how many elements an array will hold.But sometimes you may not know how many elements an array will hold.But sometimes you may not know until run time precisely how large an array you will need.To handle this situation java defines Vector class.In essence ,vector is a variable-length array of object references.That is,a vector can dynamically increase or decrease in size.Vectors are created with an initial size.When this size is exceeded ,the vector is automatically enlarged.When objects are removed,the vector may be shrunk.

public class Vector extends AbstractList implements List, Cloneable, Serializable

public Vector()

Constructs an empty vector so that its internal data array has size 10 and its standard capacity increment is zero.

public Vector(Collection c)

Constructs a vector containing the elements of the specified collection, in the order they are returned by the collection's iterator.

public Vector(int initialCapacity)

Constructs an empty vector with the specified initial capacity and with its capacity increment equal to zero.

public Vector(int initialCapacity, int capacityIncrement)

Constructs an empty vector with the specified initial capacity and capacity increment.

The common vector methods are:

boolean contains(Object elem) Returns true if the element is contained by the vector and false if it is not

Void copyInto(Object array[]) The elements contained in the invoking vector are copied into the array by array

Object elementAt(int index) Returns the component at the specified index

Enumeration elements() Returns an enumeration of the components of this vector.

void removeAllElements() Removes all components from this vector and sets its size to zero.

boolean removeElement(Object obj) Removes the first (lowest-indexed) occurrence of the argument from this vector

A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. The Map interface is shown below:

The Collection-view methods allow a Map to be viewed as a Collection in three ways:

public Set keySet();

public Collection values();

public Set entrySet();

public Set keySet()

Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined.

public Collection values():

The Collection of values contained in the Map. This Collection is not a Set, as multiple keys can map to the same value.

public Set entrySet()

The Set of key-value pairs contained in the Map.

Here's an example illustrating the standard idiom for iterating over the keys in a Map:

for (Iterator i=m.keySet().iterator(); i.hasNext(); )

System.out.println(i.next());

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

HashMap()

Constructs an empty hash map.

HashMap(Map entries)

Constructs a hash map and adds all entries from a map.

HashMap(int initialCapacity)

Constructs a new, empty map with the specified initial capacity and default load factor, which is 0.75.

HashMap(int initialCapacity, float loadFactor)

Construct an empty hash map with the specified capacity and load factor. Parameters: initialCapacity the initial number of buckets loadFactor a number between 0.0 and 1.0 that determines at what percentage of fullness the hash table will be rehashed into a larger one. The default is 0.75

public class TreeMap extends AbstractMap implements SortedMap, Cloneable, Serializable

Tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation time, depending on which constructor is used.

Constructor Summary

TreeMap()

Constructs a new, empty map, sorted according to the keys' natural order.

TreeMap(Comparator c)

Constructs a new, empty map, sorted according to the given comparator

TreeMap(Map m)

Constructs a new map containing the same mappings as the given map, sorted according to the keys' natural order.

TreeMap(SortedMap m)

Constructs a new map containing the same mappings as the given SortedMap, sorted according to the same ordering.

Collections impose no order,nor restrictions on content duplication

Lists maintain an order

Sets reject duplicate entries

Maps use unique keys to facilitate lookup of their contents

Using arrays makes insertion,deletion and growing more difficult and this problem is solved by vectors

Linked List supports insertion,deletion and growing the store,but makes indexed access slower.

Using tree supports insertion,deletion and growing the list,indexed access is slow,but searching is faster.

Using hashing supports insertion,deletion and growing the store indexed access is slow,.but searching is particularly fast.However hashing requires the use of unique keys for storing data elements.

1. Which of these are core interfaces in the collections framework?

1. Set

2. Bag

3. LinkedList

4. Collection

5. Map

2. Which of these implementations are provided by the java.util package?

1. HashList

2. HashMap

3. ArraySet

4. ArrayMap

5. TreeMap

3. What is the name of the interface used to represent collections that maintain nonunique elements in order?

1. Collection

2. Set

3. SortedSet

4. List

5. Sequence

4. What will be the result of attempting to compile and run the following program?

import java.util.*;

public class Sets

{

public static void main(String[] args)

{

HashSet set1 = new HashSet();

addRange(set1,1);

ArrayList list1 = new ArrayList();

AddRange(list1,2);

TreeSet set2 = new TreeSet();

AddRange(set2,3);

LinkedList list2 = new LinkedList();

 

set1.removeAll(list1);

list1.addAll(set2);

list2.addAll(list1);

set1.removeAll(list2);

 

System.out.println(set1);

}

static void addRange(Collection col,int step)

{

for(int i=step*2;i<=25;I+=step)

col.add(new Integer(i));

}

}

1. The program will fail to compile since operations are performed on mismatching collection implementations.

2. The program will fail to compile,since the TreeSet instance has not been given a Comparator to use when sorting its elements.

3. The program will compile without error,but will throw an UnsupportedOperationException when run.

4. The program will compile without error and will print all primes below 25 when run.

5. The program will compile without error and will print some other sequence of numbers when run.